/*
求两数之间的素数个数
*/

#include<iostream>
#include<math.h>
using namespace std;
const int MAXD=20005; // 最大的整数取值

/* 解法一 */
// 判断x是否是素数
bool isPrime(int x)
{
	// x能够被i整除
	for (int i=2; i<=(int)sqrt(x); i++)
		if (x%i==0)
			return false; // 不是素数

	// 是素数
	return true;
}

// 求a到b的素数个数
int Count1(int a, int b)
{
	// 不符合要求
	if (a>b) return 0;
	
	// 记录素数个数
	int cnt=0;
	
	// 遍历并逐一判断
	for(int x=a; x<=b; x++)
		if(isPrime(x))
			cnt++;
		
	// 返回素数个数
	return cnt;
}

void solve1(int a[],int b[],int n)
{
	for(int i=0;i<n;i++)
		printf("  %d-%d之间的素数个数=%d\n",a[i], b[i], Count1(a[i],b[i]));
}

/* 解法二：构造素数列表 */
// prime[i]=1表示i是素数
int prime[MAXD];	

// 求出 prime
void Init()
{
	// 初始认为所有数都是素数
	for(int i=0; i<=MAXD; i++)
		prime[i]=1;
	
	// 0，1不是素数
	prime[0]=prime[1]=0;
	
	// 遍历所有数
	for(int i=2; i<=MAXD; i++)
	{
		// 若i是素数
		if(prime[i])
		{
			// 则i的倍数都不是素数
			for(int j=2*i;j<=MAXD;j+=i)
				prime[j]=0;
		}
	}
}

void solve2(int a[],int b[],int n)
{
	// 构造素数列表
	Init();
	
	// prime记录0到i的素数个数
	for(int i=2; i<=MAXD; i++)
		prime[i]+=prime[i-1];
		
	// 打印结果
	for(int i=0;i<n;i++)
		printf("  %d-%d之间的素数个数=%d\n",a[i], b[i], prime[b[i]]-prime[a[i]-1]);
}
int main()
{
	// 定义数组a
	int a[]={2,5,2,3};
	
	// 求a的长度
	int n=sizeof(a)/sizeof(a[0]); 
	
	// 定义数组b
	int b[]={3,10,100,5000};
	
	printf("解法1\n"); 
	solve1(a, b, n);
	
	printf("解法2\n"); 
	solve2(a, b, n);
	
	return 0;
}
